package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         143,
		Discription: "头尾节点相连重排链表",
		Level:       2,
		Labels: map[string]int{
			"链表":   1,
			"快慢指针": 1,
		},
	})
}

func ReorderList(head *ds.ListNode) {
	mid := midNode(head)
	head2 := mid.Next
	//合并前要把前半段链表最后指向nil
	mid.Next = nil
	reverseHead2 := reverseList(head2)
	mergeList(head, reverseHead2)
}

func midNode(head *ds.ListNode) *ds.ListNode {
	fast := head
	slow := head
	for {
		if fast == nil || fast.Next == nil {
			break
		}

		fast = fast.Next.Next
		slow = slow.Next
	}

	return slow
}

func reverseList(head *ds.ListNode) *ds.ListNode {
	//反转前判空
	if head == nil {
		return nil
	}

	newHead := head
	cur := head.Next
	newHead.Next = nil
	for cur != nil {
		next := cur.Next
		cur.Next = newHead
		newHead = cur
		cur = next
	}

	return newHead
}

func mergeList(head1 *ds.ListNode, head2 *ds.ListNode) {
	for head1 != nil && head2 != nil {
		next1 := head1.Next
		next2 := head2.Next
		head1.Next = head2
		head2.Next = next1
		//防止head2的数量比head1多的情况
		if next1 == nil {
			head2.Next = next2
		}

		head1 = next1
		head2 = next2
	}
}
